package backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 90.子集||
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 */
public class subsetsWithDup {
    /**
     * 一刷
     * 思路一致，代码层面上二刷更简洁
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<>();
        int[] array = Arrays.stream(nums).sorted().toArray();
        boolean[] used = new boolean[array.length];
        for (int i = 0; i < used.length; i++) {
            used[i] = false;
        }
        backtrack(array, 0, used, res, list);
        return res;
    }

    public void backtrack(int[] nums, int start, boolean[] used, List<List<Integer>> res, List<Integer> list) {
        if (start > nums.length) {
            return;
        }
        res.add(new ArrayList<>(list));
        for (int i = start; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            list.add(nums[i]);
            used[i] = true;
            backtrack(nums, i + 1, used, res, list);
            used[i] = false;
            list.remove(list.size() - 1);
        }
    }

    /**
     * 二刷
     */
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean used[];

        public List<List<Integer>> subsetsWithDup(int[] nums) {
            used = new boolean[nums.length];
            Arrays.fill(used,false);
            Arrays.sort(nums);
            backtracking(nums, 0, used);
            return res;
        }

        public void backtracking(int[] nums, int start, boolean[] used) {

            res.add(new ArrayList<>(path));

            for (int i = start; i < nums.length; i++) {
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                    continue;
                }
                path.add(nums[i]);
                used[i] = true;
                backtracking(nums, i + 1,used);
                used[i] = false;
                path.removeLast();
            }
        }
    }




}
